package basics.algorithm.sum;

/**
 * 数组分段求和
 * 
 * @author lisy
 */
public class PreSum {
	
	/**
	 * 普通计算方法
	 */
	public static class RangeSum1 {

		private int[] arr;

		public RangeSum1(int[] array) {
			arr = array;
		}

		public int rangeSum(int L, int R) {
			int sum = 0;
			for (int i = L; i <= R; i++) {
				sum += arr[i];
			}
			return sum;
		}

	}

	/**
	 * 前缀和(help)数组计算方法 - 数据量大，查询量大
	 */
	public static class RangeSum2 {

		private int[] preSum;

		public RangeSum2(int[] array) {
			int N = array.length;
			preSum = new int[N];
			preSum[0] = array[0];
			for (int i = 1; i < N; i++) {
				preSum[i] = preSum[i - 1] + array[i];
			}
		}

		public int rangeSum(int L, int R) {
			return L == 0 ? preSum[R] : preSum[R] - preSum[L - 1];
		}

	}
	
	/**
	 * 矩阵计算方法 - 数据量一般，查询量特别大
	 */
	public  static class RangeSum3 {

		private int[][] preSum;

		public RangeSum3(int[] array) {
			int N = array.length;
			preSum = new int[N][N];
			for (int i = 0; i < N; i++) {
				for (int j = i; j < N; j++) {
					if (i == j) {
						preSum[i][j] = array[j];
					} else {
						preSum[i][j] = preSum[i][j-1] + array[j];
					}
				}
			}
		}

		public int rangeSum(int L, int R) {
			return preSum[L][R];
		}

	}
	
	public static void main(String[] args) {
		
		int[] arr = {1,2,3,4,5,6};
		
		RangeSum1 rangeSum1 = new RangeSum1(arr);
		int sum1 = rangeSum1.rangeSum(0, 4);
		System.out.println(sum1);
		
		RangeSum2 rangeSum2 = new RangeSum2(arr);
		int sum2 = rangeSum2.rangeSum(0, 4);
		System.out.println(sum2);
		
		RangeSum3 rangeSum3 = new RangeSum3(arr);
		int sum3 = rangeSum3.rangeSum(0, 4);
		System.out.println(sum3);
	}
}
